package GreedyAlgorithm;

import java.util.List;

/**
 * 邀请员工参加宴会，如何让邀请的人的快乐总和最大
 * 限制1：邀请了员工的上级，不会来了
 *
 * @author Liaorun
 */
public class MaxHappy {

    /**
     * 员工类（多叉树）
     */
    public static class Employee {

        /**
         * 这名员工的快乐值
         */
        public int happy;

        /**
         * 这名员工有那些下级
         */
        public List<Employee> nexts;
    }


    public static int maxHappy(Employee boss) {
        Info headInfo = process(boss);

        return Math.max(headInfo.laiMaxHappy, headInfo.buMaxHappy);
    }

    private static Info process(Employee x) {
        // base case, 叶节点
        if (x.nexts.isEmpty()) {
            // 叶节点来最大值就是本身快乐值，不来就是0
            return new Info(x.happy, 0);
        }
        // x 来的时候，整颗树最大收益
        int lai = x.happy;
        // x 不来的时候，整颗树最大收益
        int bu = 0;

        for (Employee next : x.nexts) {
            Info info = process(next);
            // 第一种情况：当前员工节点来了，只能加上下级不来情况下的快乐
            lai += info.buMaxHappy;
            // 第二种情况：当前员工节点不来了，加上下级不来和来的情况下，其中的快乐值较大的
            bu += Math.max(info.laiMaxHappy, info.buMaxHappy);
        }

        return new Info(lai, bu);
    }

    public static int maxHappy(int[] matrix) {
        int[][] dp = new int[matrix.length][2];
        boolean[] visited = new boolean[matrix.length];

        int root = 0;
        return 0;
    }

    private static class Info {
        /**
         * 当前员工来参加时，宴会能获得的最大快乐
         */
        public int laiMaxHappy;
        /**
         * 当前员工不来参加时，宴会能获得的最大快乐
         */
        public int buMaxHappy;

        public Info(int laiMaxHappy, int buMaxHappy) {
            this.laiMaxHappy = laiMaxHappy;
            this.buMaxHappy = buMaxHappy;
        }
    }
}
